package LeetCodeHot100TopInterview;

import java.util.ArrayList;
import java.util.List;


public class Q022_GenerateParenthesis {
    static public List<String> ans; //答案收集
    //生成所有有效括号
    //暴力怎么搞 ==> 深度优先遍历可破
    //左括号必须要右括号来匹配
    public List<String> generateParenthesis(int n) {
        //刷新 ans
        ans = new ArrayList<>();
        process(n, 0, 0, n, new StringBuilder());
        return ans;
    }
    //暴力搞
    //难点在于搞清楚 ==> 有左才有右 ==> 同生共死
    public void process(int leftRest, int rightRest, int index, int n, StringBuilder sb) {
        if (index == 2 * n ){ //从 0 开始
            ans.add(sb.toString());
            return;
        }
        if (leftRest > 0){
            sb.append("(");
            process(leftRest - 1, rightRest + 1,index + 1, n, sb);
            sb.deleteCharAt(index);
        }
        if (rightRest > 0){
            sb.append(")");
            process(leftRest, rightRest - 1,index + 1, n, sb);
            sb.deleteCharAt(index);
        }
    }

    public static void main(String[] args) {
        Q022_GenerateParenthesis fun = new Q022_GenerateParenthesis();
        fun.generateParenthesis(2);
    }
}
